1. Field of the Invention
The present invention is directed to computer systems; and more particularly, it is directed to the rendering of curves using computer systems.
2. Description of the Related Art
As the power and complexity of personal computer systems increase, graphics operations are increasingly being performed using dedicated graphics rendering devices referred to as graphics processing units (GPUs). As used herein, the terms “graphics processing unit” and “graphics processor” are used interchangeably. GPUs are often used in removable graphics cards that are coupled to a motherboard via a standardized bus (e.g., AGP or PCI Express). GPUs may also be used in game consoles and in integrated graphics solutions (e.g., for use in some portable computers and lower-cost desktop computers). Although GPUs vary in their capabilities, they may typically be used to perform such tasks as rendering of two-dimensional (2D) graphical data, rendering of three-dimensional (3D) graphical data, accelerated rendering of graphical user interface (GUI) display elements, and digital video playback. A GPU may implement one or more application programmer interfaces (APIs) that permit programmers to invoke the functionality of the GPU.
A GPU may include various built-in and configurable structures for rendering digital images to an imaging device. Digital images may include raster graphics, vector graphics, or a combination thereof. Raster graphics data (also referred to herein as bitmaps) may be stored and manipulated as a grid of individual picture elements called pixels. A bitmap may be characterized by its width and height in pixels and also by the number of bits per pixel. Commonly, a color bitmap defined in the RGB (red, green blue) color space may comprise between one and eight bits per pixel for each of the red, green, and blue channels. An alpha channel may be used to store additional data such as per-pixel transparency values.
Vector graphics data may be stored and manipulated as one or more geometric objects built with geometric primitives. The geometric primitives (e.g., points, lines, polygons, Bézier curves, and text characters) may be based upon mathematical equations to represent parts of vector graphics data in digital images. The geometric objects may typically be located in two-dimensional or three-dimensional space. To render vector graphics on raster-based imaging devices (e.g., most display devices and printers), the geometric objects are typically converted to raster graphics data in a process called rasterization.
Graphical data may often be expressed in a structured format that complies with a particular specification or model for representing such data. Instead of requiring application programs to describe every page as a full-resolution pixel array, a high-level imaging model may enable applications to describe the appearance of pages containing text, graphical shapes, and sampled images in terms of abstract graphical elements rather than directly in terms of device pixels. Such specifications and models may often be implemented across multiple computing platforms to facilitate the exchange of graphical data. The Adobe® PostScript® language, Adobe® Portable Document Format, and Adobe® Imaging Model, for example, include various structures and commands to describe complex two-dimensional graphical data including geometric models and bitmapped images.
One geometric object used in the Adobe® Imaging Model is the Bézier curve. A cubic Bézier curve is a parametric curve defined by four points (P0, P1, P2, P3) in a plane or in three-dimensional space. The curve starts at P0 and ends at P3; the curve is influenced by the position of the control points P1 and P2 relative to the endpoints P0 and P3. Similarly, a quadratic Bézier curve is a parametric curve defined by two endpoints and an additional control point. In the Adobe® PostScript® language and the Adobe® Imaging Model, a Bézier curve is defined by the “curveto” operation applied to the control points.
A typical approach to rendering a cubic Bézier curve is to “flatten” the curve by breaking it into a series of line segments that approximate the shape of the original curve. Another approach for rendering cubic Bézier curves is described in “Resolution Independent Curve Rendering Using Programmable Graphics Hardware” (Charles Loop and Jim Blinn, ACM SIGGRAPH 2005, pages 1000-1009). The cubic Bézier curve is associated with two triangles, and the parameters of the cubic Bézier curve are sent to the GPU as the attributes of the vertices of the two triangles corresponding to the cubic Bézier curve. To render the cubic Bézier curve directly in the GPU, three parameters needed for evaluation of the cubic Bézier curve are sent to the GPU as three vertex attributes for each vertex. Additionally, information determining which side of the cubic Bézier curve to render is sent to the GPU (e.g., as another vertex attribute). However, evaluation of the parameters of the cubic Bézier curve may involve expensive matrix and/or vector operations. Additionally, each cubic Bézier curve may need to be classified according to its degree of complexity (e.g., whether it includes loops, self-intersection, etc.). Furthermore, numerical computation may be insufficiently robust for a cubic Bézier curve exhibiting singularities at or near cusps and sharp discontinuities.